package LeetCode.leetcode;

/**
 * @author leiwenkang <leiwenkang@kuaishou.com>
 * Created on 2022-07-29
 */
public class Test416分割等和子集 {
    public static void main(String[] args) {
        int[] nums = new int[]{1,5,11,5};
        System.out.println(canPartition(nums));
    }

    public static boolean canPartition(int[] nums) {
        if (nums == null || nums.length == 0) {
            return false;
        }

        int sum = 0;
        int max = nums[0];

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > max) {
                max = nums[i];
            }
            sum += nums[i];
        }

        if ((sum & 1) == 1) {
            return false;
        }

        int target = sum / 2;
        if (max > target) {
            return false;
        }

        boolean dp[] = new boolean[target + 1];
        dp[0] = true;

        for (int i = 0; i < nums.length; i++) {
            for (int j = target; j >= nums[i]; j--) {
                dp[j] = dp[j] | dp[j - nums[i]];
            }
        }

        return dp[target];
    }
}
